package com.itheima.datastructure.binarysearchtree;

import com.itheima.datastructure.binarysearchtree.binarytree.TreeNode;

//二叉搜索树删除指定节点
public class E01Leetcode450 {
    public TreeNode deleteNode(TreeNode node,int key){
        if(node==null){
            return null;
        }
        if(key<node.val){
            node.left=deleteNode(node.left,key);
            return node;
        }
        if(key>node.val){
            node.right=deleteNode(node.right,key);
            return node;
        }
        if(node.left==null){
            //只有右孩子
            return node.right;
        }
        if(node.right==null){
            //只有左孩子
            return node.left;
        }
        //左右孩子都有
        TreeNode s=node.right;
        while(s.left!=null){
            s=s.left;
        }
        //后继节点处理后事
        s.right=deleteNode(node.right,s.val);
        s.left=node.left;
        return s;

    }
}
